package algorithm.josephu;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        //构造环形
        node1.next = node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node1;
        josepfu(node1,3);
    }

    /**
     *
     * @param first 环形链表的第一个
     * @param num 数几个删除
     */
    public static void josepfu(ListNode first,int num){
        //定义一个ArrayList接收
        List<Integer> list = new ArrayList<Integer>();
        //定义指针指向first的前一个节点
        ListNode t =first;
        while (t.next != first){
            t= t.next;
        }
        //

        while (first != t){
            for (int i = 0; i < num-1; i++) {
                t = t.next;
                first = first.next;
            }
            //删除节点
            t.next = first.next;
            list.add(first.val);
            first = first.next;
        }
        //剩下最后一个节点
        list.add(first.val);

        //打印
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.printf("%d\t",iterator.next());
        }
    }
}
